package org.algorithm.wE1.链表;

import org.algorithm.biubiu.wheel_1.common.ListNode;
import org.junit.Test;

/**
 * @Date 2022/2/16
 * @Desc {https://leetcode-cn.com/problems/reverse-linked-list-ii/}
 */
public class 反转链表2 {



    @Test
    public void test(){
        ListNode node = ListNode.build(1,2,3,4,5);
        ListNode res = reverseList2(node,2,4);
        System.out.println(ListNode.print(res));

    }

    public ListNode reverseList2(ListNode head, int m, int n) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        //m-1
        ListNode pre = dummyNode;
        for (int i = 0; i <m-1 ; i++) {
            pre = pre.next;
        }
        //n
        ListNode rightNode = pre;
        for (int i = 0; i <n-m+1 ; i++) {
            rightNode = rightNode.next;
        }
        //确定切分点 pre -> leftNode -> ...... ->rightNode -> curr
        ListNode leftNode = pre.next;
        ListNode curr = rightNode.next;
        //截断 pre X leftNode -> ...... ->rightNode X curr
        pre.next = null;
        rightNode.next = null;
        //翻转 leftNode <- ...... <- rightNode
        reverse(leftNode);
        //拼接 curr <- leftNode <- ...... <- rightNode <- pre
        pre.next = rightNode;
        leftNode.next = curr;
        return  dummyNode.next;
    }

    private void reverse(ListNode head){
        if(head == null || head.next == null){
            return;
        }
        ListNode pre = null;
        ListNode curr = head;
        while(curr != null){
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
    }
}
